package com.ly.algorithm.DataStructures.search;

import java.util.ArrayList;
import java.util.List;

/**
 * @Classname BinarySearch
 * @Description TODO
 * @Date 2020/4/25 9:53
 * @Author 冷心影翼
 */
public class BinarySearch {


    public static void main(String[] args) {
        int[] arr = {1,3,5,7,9,11,15,27,81};
//        int[] arr = {9,9,9,9,9,9};
        System.out.println(search2(arr, 0, arr.length - 1, 81));
    }

    public static List search(int[] arr,int left,int right,int value) {

        if(left>right ||  value<arr[0] || value>arr[arr.length-1]) {
            return new ArrayList();
        }
        int mid = (left+right)/2;
        if(arr[mid]>value) {
            return search(arr,left,mid,value);
        }else if(arr[mid] == value){
            List<Integer> list = new ArrayList<>();
            list.add(mid);
            int index = mid-1;
            while (true) {
                if(index<0 || arr[index] != value) {
                   break;
                }else {
                   list.add(index);
                   index--;
                }
            }
            index = mid+1;
            while (true) {
                if(index>arr.length-1 || arr[index]!=value  ) {
                    break;
                }else {
                    list.add(index);
                    index++;
                }
            }
            return list;
        }else {
            return search(arr,mid+1,right,value);
        }
    }

    public static int search2(int[] arr,int left,int right,int value) {
        while (left <= right) {
            int mid = (left+right)/2;
            if(arr[mid] == value) {
                return mid;
            }else if(arr[mid]>value) {
                right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return -1;
    }
}
